package dwa;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.text.ParseException;
import java.util.StringTokenizer;

/**
 *
 * @author Wichrowski
 */
public class VertexCoverTest {
// This is the part of definition of vertices and function "compareTo"  

    static class MyVertex extends Wierzcholek implements Sort.Comparable {

        public MyVertex(int r, int i) {
            super(r, i);
        }

        public int compareTo(Object other) {
            if (this.number() > (((MyVertex) other).number())) {
                return 1;
            } else if (this.number() == (((MyVertex) other).number())) {
                return 0;
            } else {
                return -1;
            }
        }
    }

// This is a routine for edge input 
    public static Krawedz readData() {
        int x;
        int y; // the number we wish to read
        try {
            InputStreamReader isr
                    = new InputStreamReader(System.in);
            BufferedReader br
                    = new BufferedReader(isr);
            String s = br.readLine();
            StringTokenizer t = new StringTokenizer(s, " ");
            x = Integer.parseInt(t.nextToken());
            y = Integer.parseInt(t.nextToken());
        } catch (IOException e) {
            x = 0;
            y = 0;
        }
        Krawedz ed = new Krawedz(x, y);
        return ed;
    }

// This is a routine for input of the number of vertex and edge
    public static int readint() {
        int a;
        try {
            InputStreamReader isr
                    = new InputStreamReader(System.in);
            BufferedReader br
                    = new BufferedReader(isr);
            String s = br.readLine();
            DecimalFormat df = new DecimalFormat();
            Number n = df.parse(s);
            a = n.intValue();
        } catch (IOException e) {
            a = 0;
        } catch (ParseException e) {
            a = 0;
        }
        return a;
    }

// main method
    public static void main(String[] args) {
        System.out.println("Podaj liczbę wierzchołków");
        int liczbaWierzcholkow = readint();

        System.out.println("Podaj liczbę krawędzi");
        int liczbaKrawedzi = readint();

        Krawedz[] tablicaKrawedzi = new Krawedz[liczbaKrawedzi];

        System.out.println("Podaj te krawedzie");
        for (int i = 0; i < liczbaKrawedzi; i++) {
            tablicaKrawedzi[i] = readData();
        }

        int[] tmp = new int[liczbaWierzcholkow + 1];
        //initialization
        for (int i = 0; i < liczbaWierzcholkow; i++) {
            tmp[i] = 0;
        }

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            for (int j = 0; j < liczbaKrawedzi; j++) {
                if (((i + 1) == tablicaKrawedzi[j].getPoprzednik()) || ((i + 1) == tablicaKrawedzi[j].getNastepnik())) {
                    tmp[i] += 1;
                }
            }
        }

        MyVertex[] v = new MyVertex[liczbaWierzcholkow];
        for (int i = 0; i < liczbaWierzcholkow; i++) {
            v[i] = new MyVertex(i + 1, tmp[i]);
        }

// Input print
        for (int i = 0; i < liczbaWierzcholkow; i++) {
            System.out.println("\n vertex : " + v[i]);
        }
        for (int i = 0; i < liczbaKrawedzi; i++) {
            System.out.println("\n edge : " + tablicaKrawedzi[i]);
        }

// "Sort" is the function of searching the vertex with largest degree corresponds to 
// covering the largest edge subset with a single vertex.
        Sort.st(v);
// v[0] is the one.

// From this, main algorithm for search "Vertex Cover"
        int[] cover = new int[liczbaWierzcholkow];
        for (int i = 0; i < liczbaWierzcholkow; i++) {
            for (int j = 0; j < liczbaKrawedzi; j++) {
                //If there are edges adjacentto v[0], add v[0] to the set of vertex cover.
                //And remove v[0] and edges incident to v[0].
                if ((v[0].kind() == tablicaKrawedzi[j].getPoprzednik())) {
                    for (int k = 0; k < liczbaWierzcholkow; k++) {
                        if (v[k].kind() == tablicaKrawedzi[j].getNastepnik()) {
                            v[k] = new MyVertex(v[k].kind(), v[k].number() - 1);
                        }
                    }
                    // This is the part of adding v[0] to the set of vertex cover.
                    cover[i] = v[0].kind();

                    // This is the part of removing v[0] and edges incident to v[0].
                    v[0] = new MyVertex(v[0].kind(), 0);
                    tablicaKrawedzi[j] = new Krawedz(0, 0);
                } // Similar to above description. 
                else if ((v[0].kind() == tablicaKrawedzi[j].getNastepnik())) {
                    for (int k = 0; k < liczbaWierzcholkow; k++) {
                        if (v[k].kind() == tablicaKrawedzi[j].getPoprzednik()) {
                            v[k] = new MyVertex(v[k].kind(), v[k].number() - 1);
                        }
                    }
                    cover[i] = v[0].kind();
                    v[0] = new MyVertex(v[0].kind(), 0);
                    tablicaKrawedzi[j] = new Krawedz(0, 0);
                }
            }
            //Now, the vertex with largest degree corresponds to covering the largest edge subset with a single vertex
            //is changed. Then we need to search new v[0].
            Sort.st(v);
        }

// Output(vertex cover set) print
        System.out.println("\n=======Vertex Cover=========");
        for (int i = 0; i < liczbaWierzcholkow; i++) {
            int j = i + 1;
            if (cover[i] != 0) {
                System.out.println("\n" + j + "th element : " + cover[i]);
            }
        }
    }
}
